import copy
import json

grammar2 = {
    "terminals": {"+", "(", ")", "id", "*", "epsilon"},
    "non_terminals": {"E", "E'", "T", "T'", "F"},
    "start": "E",
    "productions": [
        ("E", ["T", "E'"]),  # E=T E'
        ("E'", ["+", "T", "E'"]),  # E'=+ T E'
        ("E'", ["epsilon"]),  # E'=ε
        ("T", ["F", "T'"]),  # T=F T'
        ("T'", ["*", "F", "T'"]),  # T'=* F T'
        ("T'", ["epsilon"]),  # T'=ε
        ("F", ["(", "E", ")"]),  # F=( E )
        ("F", ["id"]),  # F=id
    ],
}

# 计算FIRST集
def First(grammar):
    """
    计算给定文法的First集合
    
    Args:
        grammar (dict): 文法信息，包括非终结符、终结符、产生式等
    
    Returns:
        dict: 包含每个符号的First集合的字典
    
    """
    FirstDict = {}
    for symbol in grammar["non_terminals"]:
        newDict = {symbol: set()}
        FirstDict.update(newDict)
    for symbol in grammar["terminals"]:  # rule 1
        newDict = {symbol: set()}
        FirstDict.update(newDict)
        FirstDict[symbol].update({symbol})
    LastDict = {}
    changed = True
    while changed:  # 如果First集有变化，就继续循环
        for production in grammar["productions"]:
            leftSymbol, rightList = production
            if rightList[0] in grammar["terminals"]:  # rule 2
                newSet = FirstDict[rightList[0]]
                FirstDict[leftSymbol].update(newSet)
            else:
                newSet = FirstDict[rightList[0]]
                newSet.discard("epsilon")
                FirstDict[leftSymbol].update(newSet)
        for production in grammar["productions"]:
            for i in range(0, len(rightList) - 1):  # rule 3
                symbol = rightList[i]
                nextsymbol = rightList[i + 1]
                if symbol in grammar["non_terminals"]:
                    if "epsilon" in FirstDict[symbol]:
                        newSet = FirstDict[nextsymbol].discard("epsilon")
                        # 右边不含epsilon的第一个非终结符的First集
                        newDict = {leftSymbol: {newSet}}
                        FirstDict.update(newDict)
            for i in range(0, len(rightList)):  # rule 3
                # 全部为非终结符，并且First集都包含epsilon
                if i < len(rightList) - 1:  # 如果还有下一个符号
                    symbol = rightList[i]
                    if not (
                        (symbol in grammar["non_terminals"])
                        and ("epsilon" in FirstDict[symbol])
                    ):
                        break
                    if (
                        i == len(rightList) - 1
                    ):  # 全部为非终结符，并且First集都包含epsilon
                        newDict = {leftSymbol: {"epsilon"}}
                        FirstDict.update(newDict)
        if LastDict == FirstDict:  # First集是否有变化
            changed = False
        LastDict = copy.deepcopy(FirstDict)
    return FirstDict

# 计算符号串的FIRST集
def FirstSetOfString(inputList, grammar):
    """
    inputList: 符号列表
    grammar：语法
    计算串的FIRST集
    计算一个符号串X1X2...XN的FIRST集合，计算规则
    RULE 1: 如果Xi是终结符：直接将Xi加入FIRST(X1X2...XN)集合中，并停止进一步处理该符号串。
    RULE 2 如果Xi是非终结符：
        获取FIRST(Xi)集合。
        如果FIRST(Xi)集合中不包含空串ε，则将FIRST(Xi)中的所有元素加入到FIRST(X1X2...XN)集合中，并停止对Xi之后的符号串的处理。
        如果FIRST(Xi)集合中包含空串ε，则将FIRST(Xi)中的所有非空元素加入到FIRST(X1X2...XN)集合中，并继续处理Xi+1。
    """

    FirstSet = First(grammar)  # 先得到FIRST集
    StrFirstSet = set()  # 用set()保存
    # for symbol in inputList:
    for i in range(len(inputList)):
        symbol = inputList[i]
        # Rule 1
        if symbol in grammar["terminals"]:  # 终结符
            StrFirstSet.update([symbol])
            return StrFirstSet
        # Rule 2
        if symbol in grammar["non_terminals"]:  # 终结符
            getSet = set(FirstSet[symbol])
            getSet.discard("epsilon")
            StrFirstSet.update(getSet)
            if "epsilon" not in getSet:  # 如果当前非终结符可以产生ε
                break
        if i == len(inputList) - 1:
            # 全部都含有空字
            nullStr = set(
                [
                    "epsilon",
                ]
            )
            StrFirstSet.update(nullStr)
    return StrFirstSet

# 计算FOLLOW集
def Follow(grammar):
    FirstSet = First(grammar)  # 先得到FIRST集
    # 初始化FOLLOW集
    FollowDict = {non_terminal: set() for non_terminal in grammar["non_terminals"]}
    # rule 1
    if grammar["start"] in FollowDict:
        FollowDict[grammar["start"]].add("#")  # 停止符号，有的教材用$
    FollowSetsLast = set()  # 保存现在的FOLLOW集
    changed = True
    while changed:  # 如果FOLLOW集有变化，就继续循环
        for left, rightList in grammar["productions"]:
            # rule 2,3 ，后一项非终极符的First集，加到前一项非终结符的FOLLOW集中
            for i in range(len(rightList)):  # 遍历产生式右侧的符号
                element1 = rightList[i]
                # 后一个元素的FIRST集,加到前一个元素的FOLLOW集中
                if i < len(rightList) - 1:  # 如果还有下一个符号
                    element2 = rightList[i + 1]
                    if element1 in grammar["non_terminals"]:
                        # 后一个的FIRST集（除掉epsilon）加到前一个元素的FOLLOW集中
                        theFollowSet1 = FollowDict[element1]
                        theFirstSet2 = FirstSet[element2]
                        theFirstSet2.discard("epsilon")
                        theFollowSet1.update(theFirstSet2)
                        FollowDict[element1].update(theFollowSet1)
                        # 后一个的FOLLOW集加到前一个元素的FOLLOW集中
                        if element2 in grammar["non_terminals"]:
                            theFollowSet2 = FollowDict[element2]
                            FollowDict[element1].update(theFollowSet2)
                else:  # 如果没有后一个符了
                    element1 = rightList[i]
                    if element1 in grammar["non_terminals"]:  # 如果是非终结符
                        theFollowSet1 = FollowDict[left]  # 生成式左边的FOLLOW集
                        FollowDict[element1].update(theFollowSet1)

        # FOLLOW集是否有变化
        if FollowSetsLast == FollowDict:
            changed = False
        FollowSetsLast = copy.deepcopy(FollowDict)  # 保存现在的FOLLOW集
    return FollowDict

# 计算SELECT集
def Select(grammar):
    # 对于文法G中的每个产生式A → α | β | ... | ω (这里α, β, ..., ω 是由终结符和非终结符组成的字符串)，SELECT 集定义如下：
    # Rule 1: 如果α的第一个符号是一个终结符a，则a ∈ SELECT(A → α)。
    # Rule 2:
    # 如果α的第一个符号是一个非终结符B，并且FIRST(B)中不含ε（空串），则将FIRST(B)加入到 SELECT(A → α) 。
    # 如果α的第一个符号是一个非终结符B，并且ε ∈ FIRST(B)，那么除了将FIRST(B) - {ε} 加入到 SELECT(A → α) 中外，还需要考虑α的剩余部分。如果α = Bβ，则还需计算ε ∈ FIRST(β)的情况。
    # Rule 3：如果α可以推导出ε，那么FOLLOW(A) ∪ {ε} ⊆ SELECT(A → α)，其中FOLLOW(A)表示跟随集合，即所有可能出现在A后面的终结符集合。
    FirstSet = First(grammar)  # 先得到FIRST集
    FollowSet = Follow(grammar)
    SelectDict = {}  # SELECT集，用字典来保存
    pdtCount = len(grammar["productions"])
    for i in range(0, pdtCount):
        newDict = {i: set()}
        SelectDict.update(newDict)
        pdtLeft, pdtRight = grammar["productions"][i]
        for j in range(0, len(pdtRight)):  # 遍历产生式右侧的符号
            # Rule 1
            if pdtRight[j] in grammar["terminals"]:  # 如果当前符号是终结符
                getFirstSet = FirstSet[pdtRight[j]]
                if "epsilon" in getFirstSet:
                    SelectDict[i].update(FollowSet[pdtLeft])  # Rule 3
                else:
                    SelectDict[i].update([pdtRight[j]])
                break  # 如果当前符号是终结符，则结束循环
            # Rule 2
            if (
                pdtRight[j] in grammar["non_terminals"]
            ):  # 如果当前符号是非终结符，则将该非终结符的FIRST
                getFirstSet = FirstSet[pdtRight[j]]
                if (
                    "epsilon" not in getFirstSet
                ):  # 如果FIRST集包含空字，则将FOLLOW集加入到SELECT中
                    SelectDict[i].update(getFirstSet)
                    break
                # 继续计算剩余部分，还未遇到终结符以及不包含epsilon的非终结符号
                if (
                    "epsilon" in getFirstSet
                ):  # 如果FIRST集包含空字，则将FOLLOW集加入到SELECT中
                    getFirstSet.discard("epsilon")
                    SelectDict[i].update(getFirstSet)
            # Rule 3
            if (
                j == len(pdtRight) - 1
            ):  # 如果当前符号是最后一个符号，则将FOLLOW集加入到SELECT中
                SelectDict[i].update(FollowSet[pdtLeft])
    return SelectDict

# LL1分析器
def Check(inputSymbols, grammar):
    InputStack = []  # 输入符号串的栈
    PdtStack = []  # 产生式的栈
    SelectDict = Select(grammar)
    # 将输入符号串入栈中
    inputSymbolsCount = len(inputSymbols)
    for i in range(inputSymbolsCount):
        InputStack.append(inputSymbols[inputSymbolsCount-1-i])  # 将输入符号串入栈中
    PdtStack.append("#")  # 产生式栈中加入结束符
    PdtStack.append(grammar2["start"])  # 压入开始符号
    #开始语法检测
    while len(InputStack) != 0:
        print(f"匹配栈：{PdtStack} 输入符号串栈：{InputStack}")
        if InputStack[-1] == PdtStack[-1]:  # 栈顶符号在SELECT中
            InputStack.pop()  # 弹出输入符号串的栈顶元素
            PdtStack.pop()
            continue
        #从SELECT集中选用匹配规则
        pdtSymbol = PdtStack[-1]  # 获取当前产生式的非终结符
        pdtCount = len(grammar["productions"])  
        matched = False
        for i in range(0, pdtCount):  
            if matched == True:
                break  # 如果匹配成功，则结束循环
            pdtLeft,pdtRight = grammar["productions"][i]  # 获取当前产生式的左右两部分
            if pdtLeft == pdtSymbol:
                #该产生式包括要匹配的符号，开始检查SELECT集                            
                if (InputStack[-1] in SelectDict[i]) : # 栈顶符号在SELECT中
                    if 'epsilon' in pdtRight:  # 如果为'epsilon'
                        PdtStack.pop() # 当前符号替换为空
                    else:                            
                        PdtStack.pop()  # 弹出产生式的栈顶元素
                        pdtRightCount = len(pdtRight)
                        for j in range(0, pdtRightCount):  # 将当前产生式压入栈中
                            PdtStack.append(pdtRight[pdtRightCount-1-j])
                    matched = True
                    break

    #如果产生式栈为空，则语法检测成功
    if (len(PdtStack) == 0) and (len(InputStack) == 0):
        return True   
    
    return False

# 生成所使用的的产生式列表
def GenerateProductionList(inputSymbols, grammar):
    """
    语法树生成函数
    
    Args:
        inputSymbols (list): 输入符号列表
        grammar (dict): 语法规则字典
    
    Returns:
        list: 语法树列表
    
    """
    OutList = []
    InputStack = []  # 输入符号串的栈
    ProductStack = []  # 产生式的栈
    SelectDict = Select(grammar)
    # 将输入符号串入栈中
    inputSymbolsCount = len(inputSymbols)
    for i in range(inputSymbolsCount):
        InputStack.append(inputSymbols[inputSymbolsCount-1-i])  # 将输入符号串入栈中,逆向入栈
    ProductStack.append("#")  # 产生式栈中加入结束符
    ProductStack.append(grammar2["start"])  # 压入开始符号
    #开始语法检测
    while len(InputStack) != 0:
        print(f"匹配栈：{ProductStack} 输入符号串栈：{InputStack}")
        if InputStack[-1] == ProductStack[-1]:  # 匹配一个删除一个
            InputStack.pop()  # 弹出输入符号串的栈顶元素
            ProductStack.pop()
            continue
        #从SELECT集中选用匹配规则
        pdtSymbol = ProductStack[-1]  # 获取当前产生式的非终结符
        pdtCount = len(grammar["productions"])  
        matched = False
        for i in range(0, pdtCount):  
            if matched == True:
                break  # 如果匹配成功，则结束循环
            pdtLeft,pdtRight = grammar["productions"][i]  # 获取当前产生式的左右两部分
            if pdtLeft == pdtSymbol:
                #该产生式包括要匹配的符号，开始检查SELECT集                            
                if (InputStack[-1] in SelectDict[i]) : # 栈顶符号在SELECT中
                    # 栈顶的符号用产生式来产生
                    OutList.append(grammar["productions"][i])
                    print(f"{pdtLeft}→{pdtRight}")
                    if 'epsilon' in pdtRight:  # 如果为'epsilon'
                        ProductStack.pop() # 当前符号替换为空
                    else:                            
                        ProductStack.pop()  # 弹出产生式的栈顶元素
                        pdtRightCount = len(pdtRight)
                        for j in range(0, pdtRightCount):  # 将当前产生式压入栈中
                            ProductStack.append(pdtRight[pdtRightCount-1-j])
                    matched = True
                    break
    #如果产生式栈为空，则语法检测成功
    if (len(ProductStack) == 0) and (len(InputStack) == 0):
        print(OutList)
    
    return OutList

#递归实现从产生式生成语法树
def SyntaxTree(productionList, index=0, grammar=None):
    """
    根据产生式列表生成语法树
    
    Args:
        productionList (list): 产生式列表
        index (int): 当前产生式索引
        grammar (dict): 语法规则
    
    Returns:
        dict: 语法树字典
    
    """
    TreeDict = {'name': '', 'children': []}
    if index < len(productionList):
        left, right = productionList[index]
        TreeDict['name'] = left  # 设置节点的名字
        ProdIndexOffset = index + 1  # 产生式索引偏移量
        for i in range(len(right)):
            if right[i] in grammar['terminals']:  # 如果是终结符,没有子节点
                child = {'name': right[i], 'children': []}
                TreeDict['children'].append(child)
            else:  # 如果是非终结符,有子节点
                NT = right[i]  # 找到该非终结符对应的产生式
                for j in range(ProdIndexOffset, len(productionList)):  # 从后边的列表元素中找到最先匹配的该非终结符的产生式
                    if NT == productionList[j][0]: # 找到该非终结符对应的最近的一个产生式，并使用
                        child = SyntaxTree(productionList, j, grammar)
                        TreeDict['children'].append(child)
                        ProdIndexOffset = ProdIndexOffset + 1 #下一个非终结符，从后边的产生式中查找
                        break
    return TreeDict


inputSymbolsList = ["id","+","id","*","id","#"]
rst = Check(inputSymbolsList, grammar2)
# print(rst)
ProductionList = []
if rst:
    print("生成语法树-------------------------------------------")
    ProductionList= GenerateProductionList(inputSymbolsList, grammar2)



Tree = SyntaxTree(ProductionList,index=0,grammar=grammar2)
print(json.dumps(Tree, indent=4))

